package org.example.myleet.p1104;

import java.util.LinkedList;
import java.util.List;

/**
 * 题目链接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/
 * 完全二叉树的节点编号见图
 * 思路：
 * 对于一个label值，首先我们要找到这个label在第几层的节点
 * 找到层数之后，观察二叉树叶子节点，发现其对应的父节点存在这样的关系：
 * 将每一层看作一个数组，label的父节点的索引的计算方法是：idx = Math.ceil((label - pow + 1) / 2.0)
 * 其中，pow = 2^(level - 1)，意即label在当前层数组的索引除以2，然后向上取整
 * 例如：[15,14,13,12,11,10,9,8]，label=14，level=4，计算得到label父节点的索引idx是4（Math.ceil((14 - 8 + 1) / 2.0) = 4）
 * 说明其父节点在从右边开始往左边数第四个位置（从1开始数），即[4,5,6,7]中的4，这里之所以从右边开始往左边数是因为
 * [15,14,13,12,11,10,9,8]的顺序是从右往左排的，如果题目全部是从左往右排列标记的话，也是可以的，注意观察计算出来的下标与叶子节点的关系
 * 即最终叶子节点的上一级节点就是pow - idx，其中pow = 2^(level - 1)
 * 然后我们来到第三层，按照同样道理找第二层的节点，直到最终找到第一层节点
 */
public class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> result = new LinkedList<>();
        //先找到目标层
        int level = 0, pow = 1;
        for (; level <= 20; ++level) {
            pow <<= 1;
            if (label < pow) {
                break;
            }
        }
        result.add(label);
        //循环回溯节点路径
        int node = label;
        while (level > 0) {
            pow >>= 1;
            node = pow - (int) Math.ceil((node - pow + 1) / 2.0);
            result.add(0, node);
            --level;
        }
        return result;
    }
}
